#include<iostream>
#include<string.h>
#include<vector>
using namespace std;

//01背包模板
const int N = 1001;
//全局变量，默认值为0
int n, V, dp[N][N], v[N], w[N];

void test1(){
    //输入物品个数和背包容量
    cin >> n >> V;

    //输入每个物品的体积和价值
    for (int i = 1; i <= n; i++){
        cin >> v[i] >> w[i];
    }

    //问题一状态表示 dp[i][j]表示挑选前i个物品，体积不超过j的最大价值
    //初始值全部设置为0
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= V; j++){
            //如果不挑选当前i物品，找挑选前i-1个物品不超过j的最大价值
            dp[i][j] = dp[i - 1][j];
            //如果挑选当前i物品,找挑选前i-1个物品不超过j-v[i]的最大价值然后加上当前物品的价值
            //两种情况取最大值
            if (j >= v[i]){
                dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i][j]);
            }
        }
    }
    //输出结果
    cout << dp[n][V] << endl;

    //初始化状态表
    memset(dp, 0, sizeof dp);

    //问题二状态表示 dp[i][j]表示挑选前i个物品，提及恰好等于j的最大价值
    //第一行除第一个外，其他全初始值设置为-1
    for (int j = 1; j <= V; j++){
        dp[0][j] = -1;
    }
    //填表
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= V; j++){
            //如果不挑选当前i物品，找挑选前i-1个物品,体积恰好等于j的最大价值
            dp[i][j] = dp[i - 1][j];

            //如果挑选当前i物品，找挑选前i-1个物品，体积恰好等于j-v[i]的最大价值
            if (j >= v[i] && dp[i - 1][j - v[i]] != -1){
                dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i][j]);
            }
        }
    }
    //输出结果
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
}
//空间优化
int dp[N];
void test2(){
    //输入物品个数和背包体积
    cin >> n >> V;

    //输入每个物品的体积和价值
    for (int i = 1; i <= n; i++){
        cin >> v[i] >> w[i];
    }

    //问题一
    for (int i = 1; i <= n; i++){
        for (int j = V; j >= v[i]; j--){
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    //输出结果
    cout << dp[V] << endl;

    //初始化状态表
    memset(dp, 0, sizeof dp);

    //问题二
    for (int j = 1; j <= V; j++){
        dp[j] = -1;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = V; j >= v[i]; j--)
        {
            if (dp[j - v[i]] != -1){
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
    }
    //输出结果
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
}



//416.分割等和子集
bool canPartition(vector<int>& nums){
    int sum=0;
    for(auto num : nums){
        sum += num;
    }

    if (sum % 2 == 1){
        return false;
    }
    sum /= 2;
    int n = nums.size();

    //状态表示 dp[i][j]表示挑选前i个数，所有的选法中，能否恰好等于j
    vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1,true));
    //初始化 添加第0行和第0列,除第一行外其余全部为true
    for (int j = 1; j <= sum; j++){
        dp[0][j] = false;
    }

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= sum; j++){
            //当前位置i元素要么选要么不选，两种情况满足一种即可
            dp[i][j] = dp[i - 1][j];
            if (j >= nums[i - 1]){
                dp[i][j] || = dp[i - 1][j - nums[i - 1]];
            }
        }
    }

    //返回值
    return dp[n][sum];
}
//空间优化
bool canPartition2(vector<int>& nums){
    int n = nums.size();

    int sum = 0;
    for(auto num : nums){
        sum += num;
    }
    if (sum % 2 == 1){
        return false;
    }
    sum /= 2;

    //状态表示
    vector<bool> dp(sum + 1);
    //初始化
    dp[0] = true;

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = sum; j >= nums[i - 1]; j--){
            if (dp[j - nums[i - 1]] != false){
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }
    }

    //返回值
    return dp[sum];
}


//494.目标和
int findTargetSumWays(vector<int>& nums, int target){
    // 原数组分成两堆，一堆为正数，一堆为负数，假设正数的和为a，负数的和绝对值为b,原数组的和为sum
    // a-b=target&&a+b=sum  => a=(sum+target)/2;
    //转换成从原数组中挑选几个数和为a，总共有多少种选法

    int n = nums.size();
    int sum = 0;
    for(auto num : nums){
        sum += num;
    }
    if (sum + target < 0 || (sum + target) % 2 == 1){
        return 0;
    }
    int a = (sum + target) / 2;

    //状态表示 dp[i][j]表示从前i个数中挑选，和恰好为j，总共有多少种选法
    vector<vector<int>> dp(n + 1, vector<int>(a + 1));

    //初始化 dp[0][0]表示从前0个数中挑选，和恰好为0，有1种选法
    //第0行表示从前0个数中挑选，和恰好为j(j>=1)，有0种选法
    dp[0][0] = 1;

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= a; j++){
            //状态转移方程
            dp[i][j] += dp[i - 1][j];
            if (j >= nums[i - 1]){
                dp[i][j] += dp[i - 1][j - nums[i - 1]];
            }
        }
    }

    //返回值
    return dp[n][a];
}
//空间优化
int findTargetSumWays2(vector<int>& nums, int target){
    int n = nums.size();
    int sum = 0;
    for(auto num :nums){
        sum += num;
    }
    if (sum + target < 0 || (sum + target) % 2 == 1){
        return 0;
    }
    int a = (sum + target) / 2;

    //状态表示
    vector<int> dp(a + 1);
    //初始化
    dp[0] = 1;

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = a; j >= nums[i - 1]; j--){
            //状态转移方程
            dp[j] += dp[j - nums[i - 1]];
        }
    }

    //返回值
    return dp[a];
}


//1049.最后一块石头剩余的重量
int lastStoneWeightII(vector<int>& stones){
    int n = stones.size();
    int sum = 0;
    for(auto num : stones){
        sum += num;
    }
    int aim = sum / 2;

    //状态表示 dp[i][j]表示挑选前i个石头，使重量和接近j所有选法种，最大的重量
    vector<vector<int>> dp(n + 1, vector<int>(aim + 1));
    //初始化 dp[0][0]表示挑选前0个石头，使重量和接近0的最大重量，就是0
    //第0行表示挑选前0个石头，使重量和接近j(j>=1)的最大重量，就是0
    //第0列表示挑选前i(i>=1)个石头,使重量和接近0的最大重量，还是0

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= aim; j++){
            //不挑选当前i石头
            dp[i][j] = dp[i - 1][j];
            //挑选当前i石头
            if (j >= stones[i - 1]){
                dp[i][j] = max(dp[i - 1][j - stones[i - 1]] + stones[i - 1], dp[i][j]);
            }
        }
    }

    //返回值
    return sum - 2 * dp[n][aim];
}
//空间优化
int lastStoneWeightII2(vector<int>& stones){
    int n = stones.size();
    int sum = 0;
    for(auto num : stones){
        sum += num;
    }
    int aim = sum / 2;

    //状态表示
    vector<int> dp(aim + 1);

    //填表
    for (int i = 1; i <= n; i++){
        for (int j = aim; j >= stones[i - 1]; j--){
            //状态转移方程
            dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
        }
    }

    //返回值
    return sum - 2 * dp[aim];
}


int main(){
    

    return 0;
}